import java.util.Arrays;

public class KuaiSuSort {
    //快速排序
    public static void quickSort(int[] arr,int startIndex,int endIndex){
        //判断循环终止条件
        if (startIndex >= endIndex){
            return;
        }
        int i = paiXu(arr, startIndex, endIndex);
        //右侧
        quickSort(arr,startIndex,i-1);
        //左侧
        quickSort(arr,i+1,endIndex);


    }
    //拿到基准值
    public static int paiXu(int[] arr,int startIndex,int endIndex){
        int temp = startIndex;
        int right = endIndex;
        int left = startIndex;
        while (right != left){
            while ((right > left) && (arr[temp] < arr[right])){
                right--;

            }
            while((right > left) && (arr[temp] >  arr[left])){
                left++;
            }
            if (right > left){
                //变换两个指针的位置
                swap(arr,right,left);
            }



        }
        //变换基准值
        swap(arr,temp,left);

        return left;
    }
    public static void swap(int[] arr,int num1,int num2){
        int temp = arr[num1];
        arr[num1]= arr[num2];
        arr[num2]= temp;



    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 3, 1, 6};
        int n = arr.length;

        KuaiSuSort.quickSort(arr,0,n-1);
        System.out.println("arr = " + Arrays.toString(arr));
    }
}
